#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: max_path.py 
@version:
@time: 2024/01/25 

所指的路径并不一定从根节点出发到叶子节点，而是可以从任意节点到任意节点。
因此，每一棵子树都需要判断当前路径是不是最大路径。首先定义一个变量res用于保存目前最大路径的值，
接下来需要设计、访问以每个节点为根节点的树时的内部逻辑，此处用到深度优先搜索算法，一直深入到底。

访问每个节点时，分别计算其左右子树的最大路径值，只有当左右子树的最大路径值大于0时，才是能增大路径之和的。
因此，当左右子树最大路径小于0时，直接置0，然后对比更新res的值。那么每一次返回给上层的值，
是该节点与其左子树最大路径之和或者该节点与其右子树最大路径之和，因为路径是不能折回的，
这样才能保证递归返回当前节点的最大路径。
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node1.left = node2
node1.right = node3
node2.left = node4


class Max:
    res = []

    def max_path(self, root):
        self.res = float('-inf')
        self.dfs(root)
        return self.res

    def dfs(self, root):
        if not root:
            return 0
        left = max(0, self.dfs(root.left))
        right = max(0, self.dfs(root.right))
        self.res = max(self.res, left + root.val + right)
        return root.val + max(left, right)


print(Max().max_path(node1))
